package com.levi.sort;

import java.util.Arrays;

/**
 * @author shentong
 * @date 2021/9/5 17:42
 * @Description 希尔排序  交换法，每次比较都要交换元素，效率比较低
 * 核心:把数组中的元素先分为arr.length/2个数组，进行第一轮插入排序，分好组后再把数组分为arr.length/2/2个数组，在进行第二轮插入排序，
 * 直到arr.length/2=0时候，就已经排好序了
 * 核心:控制好需要进行几轮排序即可
 */
public class ShellSort {
    public static void main(String[] args) {
//        int[] array = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0};
        int[] array = new int[80000];
        for (int i = 0; i < 80000; i++) {
            array[i] = (int) (Math.random()*8000000);
        }
        long begin = System.currentTimeMillis();

//        shellSorrtExchange(array);//shell排序交换法   13857毫秒
        shellSortMove(array);//shell排序移动法     30毫秒左右
        long end = System.currentTimeMillis();
        System.out.printf("shell排序80000个元素需要%d毫秒\n",end-begin);


    }

    /**
     * 希尔排序交换法 ，效率比较低
     * a为需要进行几轮排序的次数,初始值为数组长度/2，之后都除以2，来控制循环的次数
     * @param array
     */
    public static void shellSorrtExchange(int[] array) {
        var num = 0;
        for (int a = array.length / 2; a >0 ; a = a/2) {
            for (int i = a; i < array.length; i++) {
                var temp = 0;
                for (int j = i-a; j >=0; j=j-a) {
                    if (array[j] > array[j + a]) {
                        temp = array[j];
                        array[j ] = array[j+a];
                        array[j+a] = temp;
                    }
                }
            }
//            System.out.println("第"+(++num)+"次排序的结果是:"+Arrays.toString(array));
        }





            //shell排序第一排序,分成arr.length/2组，每一组都进行插入排序
        /**
         * i = 5表示分成5组，每一组都进行一次循环,一次循环只进行一次比较，因为每一组只有两个元素
         */
//        for (int i = 5; i < array.length; i++) {
//            var temp = 0;
//            for (int j = i-5; j >=0; j=j-5) {
//                if (array[j] > array[j + 5]) {
//                    temp = array[j];
//                    array[j ] = array[j+5];
//                    array[j+5] = temp;
//                }
//            }
//        }
//        System.out.println("shell第一次排序后的顺序是:\n"+ Arrays.toString(array));
//        /**
//         * [3, 5, 1, 6, 0, 8, 9, 4, 7, 2]
//         *i = 2 j =0  j = -2
//         * i = 3 j = 1 j = -1
//         * i = 4 j = 2 j = 0
//         * i = 5 j = 3 j = 1 j = -1
//         * i = 6 j = 4 j = 2 j = 0
//         * i = 7 j = 5 j = 3 j = 1 j = -1
//         * i = 8 j = 6 j = 4 j = 2 j = 0
//         *i = 9 j = 7 j = 5 j = 3 j = 2
//         */
//        for (int i = 2; i < array.length; i++) {
//            var temp = 0;
//            for (int j = i-2; j >=0; j=j-2) {
//                if (array[j] > array[j + 2]) {
//                    temp = array[j];
//                    array[j ] = array[j+2];
//                    array[j+2] = temp;
//                }
//            }
//        }
//        System.out.println("shell第二次排序后的顺序是:\n"+ Arrays.toString(array));
//
//        for (int i = 1; i < array.length; i++) {
//            var temp = 0;
//            for (int j = i-1; j >=0; j=j-1) {
//                if (array[j] > array[j + 1]) {
//                    temp = array[j];
//                    array[j ] = array[j+1];
//                    array[j+1] = temp;
//                }
//            }
//        }
//        System.out.println("shell第三次排序后的顺序是:\n"+ Arrays.toString(array));
    }

    /**
     * 希尔排序 移动法  效率比交换法效率高
     *
     * @param arr
     */
    public static void shellSortMove(int[] arr){
        var num = 0;
        for (int flag = arr.length/2; flag >0 ; flag = flag/2) {
            //第一移动
            for (int i = flag; i < arr.length; i++) {
                var j = i;
                var temp = arr[j];
                /**
                 * 首先temp是要插入的值，跟他前面flag步长的值进行比较,如果比前面的值小，就开始循环找，让他前面flag步长的值往后移，一直找到比他大的值，
                 * 这时候退出循环，j就是要插入的索引位置
                 */
                if (temp < arr[j - flag]) {
                    while (j - flag >= 0 && temp < arr[j - flag]) {
                        arr[j] = arr[j - flag];
                        j = j - flag;
                    }
                    //退出循环后就是在好到位置的时候
                    arr[j] = temp;
                }
            }
            System.out.println("第"+(++num)+"次移动后的结果"+Arrays.toString(arr));
        }


    }
}
